package caculate;

/**
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2025-02-24 16:18
 **/
public class BoyerMoore {

    // BM算法的坏字符启发式方法
    public static int[] badCharacterHeuristic(String pattern) {
        int[] badChar = new int[256];  // ASCII字符集的大小
        for (int i = 0; i < 256; i++) {
            badChar[i] = -1;  // 初始化为-1，表示该字符在模式串中未出现
        }

        // 填充坏字符表
        for (int i = 0; i < pattern.length(); i++) {
            badChar[pattern.charAt(i)] = i;
        }

        return badChar;
    }

    // BM算法的好后缀启发式方法
    public static int[] goodSuffixHeuristic(String pattern) {
        int m = pattern.length();
        int[] goodSuffix = new int[m];
        int[] suffix = new int[m];

        // 计算后缀数组
        suffix[m - 1] = m;
        for (int i = m - 2; i >= 0; i--) {
            int j = i;
            while (j >= 0 && pattern.charAt(j) == pattern.charAt(m - 1 - (i - j))) {
                j--;
            }
            suffix[i] = i - j;
        }

        // 计算好后缀表
        for (int i = 0; i < m; i++) {
            goodSuffix[i] = m;
        }

        for (int i = 0; i < m - 1; i++) {
            goodSuffix[m - 1 - suffix[i]] = i + 1;
        }

        return goodSuffix;
    }

    // Boyer-Moore算法的搜索方法
    public static int search(String text, String pattern) {
        int[] badChar = badCharacterHeuristic(pattern);
        int[] goodSuffix = goodSuffixHeuristic(pattern);
        int m = pattern.length();
        int n = text.length();

        int s = 0;  // 搜索的开始位置
        while (s <= (n - m)) {
            int j = m - 1;

            // 从右到左检查模式串是否与文本匹配
            while (j >= 0 && pattern.charAt(j) == text.charAt(s + j)) {
                j--;
            }

            // 如果完全匹配，返回匹配位置
            if (j < 0) {
                return s;  // 找到匹配
            } else {
                // 根据坏字符规则和好后缀规则，计算模式串的移动距离
                int badCharShift = Math.max(1, j - badChar[text.charAt(s + j)]);
                int goodSuffixShift = (j < m - 1) ? goodSuffix[j + 1] : 1;
                s += Math.max(badCharShift, goodSuffixShift);
            }
        }

        return -1;  // 如果没有匹配，返回-1
    }

    // 测试方法
    public static void main(String[] args) {
        String text = "ABAAABCDABCABCDABDE";
        String pattern = "ABCD";

        int result = search(text, pattern);
        if (result != -1) {
            System.out.println("Pattern found at index: " + result);
        } else {
            System.out.println("Pattern not found");
        }

        text = "HERE IS A SIMPLE EXAMPLE";
        pattern = "EXAMPLE";
        int index = search(text, pattern);
        System.out.println("Pattern found at index: " + index); // 输出 17

        text = "ABABABCABABABD";
        pattern = "ABABD";
        index = search(text, pattern);
        System.out.println("Pattern found at index: " + index); // 输出 9

        text = "ABCDEFG";
        pattern = "XYZ";
        index = search(text, pattern);
        System.out.println("Pattern not found: " + index); // 输出 -1

    }

}
